import time
import numpy as np


def dp_bag(count: int, volume: int, weight: list[int], vlaues: list[int]) -> list[list[int]]:
    """
    :param count: 数量
    :param volume: 容量
    :param weight: 各元素重量
    :param vlaues: 价值
    :return: 动态转移的矩阵
    """
    value = [[0 for _ in range(volume + 1)] for _ in range(count + 1)]
    for i in range(1, count + 1):
        for j in range(1, volume + 1):
            value[i][j] = value[i - 1][j]
            # 背包总容量够放当前物体，遍历前一个状态考虑是否置换
            if j >= weight[i - 1] and value[i][j] < value[i - 1][j - weight[i - 1]] + vlaues[i - 1]:
                value[i][j] = value[i - 1][j - weight[i - 1]] + vlaues[i - 1]
        tmpvalue = np.array(value)
        print("第 %d 次:" % i)
        print(tmpvalue)
        print("")
    return value


def show_info(count: int, volume: int, weight: list, value: list[list[int]]):
    """
    :param count: 数量
    :param volume: 容量
    :param weight: 各元素重量
    :param value: 动态转移矩阵
    :return:
    """
    print('最大价值为:', value[count][volume])
    x = [False for _ in range(count)]
    j = volume
    for i in range(count, 0, -1):
        if value[i][j] > value[i - 1][j]:
            x[i - 1] = True
            j -= weight[i - 1]
    print('背包中所装物体为:')
    for i in range(count - 1):
        if x[i]:
            print('第', i + 1, '个', end=' ')
    print('')


def main():
    count = int(input('请输入元素个数:\n'))
    volume = int(input('请输入背包容量:\n'))
    weight = [int(count) for count in input('请输入各个元素的重量\n').split()]
    vlaues = [int(count) for count in input('请输入各个元素的价值\n').split()]
    time1 = time.perf_counter()
    dpmartix = dp_bag(count, volume, weight, vlaues)
    tmpmartix = np.array(dpmartix)
    print(tmpmartix)
    show_info(count, volume, weight, dpmartix)
    time2 = time.perf_counter()
    print("消耗时间：%f s" % (time2 - time1))


def test():
    count = int(np.random.randint(1, 15, 1))
    print("数量为：%d" % count)
    volume = int(np.random.randint(1, 15, 1))
    print("容量为：%d" % volume)
    each_weight = np.random.randint(1, 10, count).tolist()
    print("每个元素质量为:")
    print(each_weight)
    each_value = np.random.randint(1, 10, count).tolist()
    print("每个元素价值为:")
    print(each_value)
    time1 = time.perf_counter()
    dpmartix = dp_bag(count, volume, each_weight, each_value)
    # tmpmartix = np.array(dpmartix)
    # print(tmpmartix)
    show_info(count, volume, each_weight, dpmartix)
    time2 = time.perf_counter()
    print("消耗时间：%f s" % (time2 - time1))


if __name__ == '__main__':
    main()
    # test()
